/**
 *  Front Back Split
 *
 *  Given a list, split it into two sublists — one for the front half, and one for the back half. 
 *  If the number of elements is odd, the extra element should go in the front list. 
 *  So FrontBackSplit() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7, 11}.
 *
 */

class FrontBackSplit<T> {
    
    private Node head;
    private Node back;

    private class Node {
        private T item;
        private Node next;
    }

    public Node add(T item) {
        Node curr = head;
        head = new Node();
        head.item = item;
        head.next = curr;
        return head;
    }

    public String split() {
       if (head == null) {
           return "";
       }

       Node slow = head; // Slow pointer move 1 step forward
       Node fast = head; // Fast pointer move 2 steps forward
       Node front_last_node = head; // Last node of first half

       while (fast != null) {
           front_last_node = slow;
           slow = slow.next;
           fast = (fast.next != null) ? fast.next.next : null;
       }

       front_last_node.next = null;
       back = slow;

       String s1 = printList(head);
       String s2 = printList(back);

       if (s2.length() > 0) {
           return s1 + ", " + s2;
       } else {
           return s1;
       }
       
    }

    private String printList(Node head) {
        StringBuilder sb = new StringBuilder();

        Node p = head;
        while (p != null) {
            if (p != head) {
                sb.append(" ");
            }
            sb.append(p.item.toString());
            p = p.next;
        }

        return sb.toString();
    }

}
